1. Field of the Invention
The present invention relates to a line generator and a method for determining the individual pixels to be plotted for a line to be drawn in a display system, and to a display system incorporating such a line generator.
2. Background Art
To automatically draw a line on a pixel-based display screen, plotter and so on is not a trivial task. A lot of effort has been put into the solving the problem of providing a representation, within a reasonable response time, of a line on a screen, a plotter, and so on which appears accurate to the user. This task is non-trivial because a line to be drawn will, in the general case, only pass through pixel positions on the screen, plotter field and so on, which are too far apart to create a continuous line. As a result of this the system has to determine intermediate pixels positions to be used in order to approximate the line to be drawn.
Many different techniques for deciding which pixel positions are needed have been proposed, and a number of them are described in Foley and Van Dam's book "Fundamentals of Interactive Graphics" published in 1982 by Addison-Wesley Publishing Company. On pages 432 to 438 techniques for drawing straight lines are described and on pages 441 to 446 techniques for drawing other lines such as circular arcs are described. The major disadvantage of all of these prior techniques is that there is a significant amount of processing to be done each time a line is selected before that line can actually be drawn. The time take to carry out this processing (i.e. set-up and algorithm execution time) provides a significant overhead which limits the performance of the display system.
In GB -A- 2048624 (U.S. Pat. No. 4,330,834) an attempt to overcome disadvantages of the prior art is described. In cell-organized graphic display apparatus representations of segments of lines within a character cell are pre-stored and then used to plot lines on the display. In order to avoid the need to store all possible lines which could cross a cell (wholly or partially) a subset only of the possible lines are pre-stored and masking and shifting logic is provided. This further logic also provides a processing overhead which reduces the advantages of this prior approach. Also, as most of a cell is traversed by a line will be background only, inefficient use of storage is made.
The object of the present invention is to provide an efficient line generator which overcomes the difficulties of the prior art.